package com.yitiao.data_algorithms.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Stack;

/**
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如
果气温在这之后都不会升高，请在该位置用 0 来代替。 

 

 示例 1: 

 
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
 

 示例 2: 

 
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
 

 示例 3: 

 
输入: temperatures = [30,60,90]
输出: [1,1,0] 

 

 提示： 

 
 1 <= temperatures.length <= 10⁵ 
 30 <= temperatures[i] <= 100 
 
 Related Topics 栈 数组 单调栈 👍 1026 👎 0

*/
// 每日温度
// 2022-02-26 16:06:33
class DailyTemperatures{
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 返回下一个最大数的坐标与当前的差
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[temperatures.length];
        // 下一个最大数模板
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]){
                Integer pop = stack.pop();
                ans[pop]=i-pop;
            }
            // 将下标入栈，就很方便的计算差值
            stack.push(i);
        }

        return ans;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
//public static void main(String[] args) {
//    Solution solution = new Solution();
//    int [] t={73,74,75,71,69,72,76,73};
//    int[] ints = solution.dailyTemperatures(t);
//    System.out.println(ints);
//}
}